package com.jky.stmall.exercise;

import java.util.Arrays;

public class CutRod {

    //定义一个数组保存已经计算过的最优解
    static int[] r;

    public static void main(String[] args) {
        //计算长度为n的钢条的最大收益。
        //       0 1 2 3 4 5  6   7 8  9  10
        int[] p={0,1,5,8,9,10,17,17,20,24,30};
        int n =35;

        //初始化r数组
        r=new int[n+1];
        Arrays.fill(r,-1);
        int q=cutRod(p,n);
        System.out.println(q);
    }
    public static  int cutRod(int[] p,int n){
        if (n==0){
            return 0;
        }
        //尝试去缓存中取
        if(r[n]>=0){
            return r[n];
        }
        //定义一个最大收益
        int q=-1;
        int maxIndex=n>10?10:n;
        for (int i =1;i<=maxIndex;i++){
            //计算当前方案的最大收益
        int maxPrice = p[i]+cutRod(p,n-i);
        if (maxPrice>q)
            q=maxPrice;
        }
        r[n]=q;
        return q;
    }
}
